#include <cstddef>
#include <cstdint>
#include <forward_list>
#include <memory>
#include <vector>

namespace WinstJackonw {
namespace _details {}  // namespace _details
template <typename T>
class Hash;
template <>
struct Hash<int> {
  std::size_t operator()(int in) const { return in ^ (in << 1); }
};
template <typename T>
class Allocator {
 public:
  using value_type = T;
  using pointer = T*;
  using const_pointer = const T*;
  using reference = T&;
  using const_reference = const T&;
  using size_type = std::size_t;
  using difference_type = std::ptrdiff_t;
  template <typename U>
  struct rebind {
    using other = Allocator<U>;
  };
  Allocator() = default;
  Allocator(const Allocator&) = default;
  template <typename U>
  Allocator(const Allocator<U>&) {}
  Allocator& operator=(const Allocator&) = default;
  template <typename U>
  Allocator& operator=(const Allocator<U>&) {
    return *this;
  }
  template <typename U>
  Allocator& operator=(Allocator<U>&&) {
    return *this;
  }
  Allocator& operator=(Allocator&&) = default;
  pointer allocate(size_type n) {
    if (n > max_size()) {
      throw std::bad_alloc();
    }
    return static_cast<pointer>(::operator new(n * sizeof(T)));
  }

  void deallocate(pointer p, size_type) noexcept { ::operator delete(p); }

  template <typename U, typename... Args>
  void construct(U* p, Args&&... args) {
    new (p) U(std::forward<Args>(args)...);  // placement new
  }

  template <typename U>
  void destroy(U* p) {
    p->~U();
  }

  size_type max_size() const noexcept {
    return std::numeric_limits<size_type>::max() / sizeof(T);
  }

  pointer address(reference x) const noexcept { return &x; }
  const_pointer address(const_reference x) const noexcept { return &x; }
};

template <typename T, typename U>
bool operator==(const Allocator<T>&, const Allocator<U>&) noexcept {
  return true;
}

template <typename T, typename U>
bool operator!=(const Allocator<T>&, const Allocator<U>&) noexcept {
  return false;
}

template <typename TKey, typename T, typename TFHash = Hash<TKey>,
          typename TAllocator = Allocator<std::pair<const TKey, T>>>
class HashMap {
 public:
  using ValueType = std::pair<const TKey, T>;
  using KeyType = TKey;
  using Iterator = ValueType*;
  HashMap() : data(114514) {}
  std::pair<Iterator, bool> Insert(ValueType&& rhs) {
    return InsertAt(TFHash{}(rhs.first), std::move(rhs));
  }
  Iterator Find(const TKey& key) {
    auto& bucket = data[TFHash{}(key)];
    auto it = std::find_if(
        bucket.begin(), bucket.end(),
        [key](const ValueType& value) { return value.first == key; });
    return it == bucket.end() ? (Iterator) nullptr : &*it;
  }
  std::size_t Erase(const TKey& key) {
    auto& bucket = data[TFHash{}(key)];
    return bucket.remove_if([key](const ValueType& value) { return value.first == key; }); // valid since C++20 https://en.cppreference.com/w/cpp/container/forward_list/remove.html
  }

 private:
  std::pair<Iterator,bool> InsertAt(std::size_t dataPos, ValueType&& rhs) {
    auto& bucket = data[dataPos];
    auto insertPos = std::find_if(
        bucket.begin(), bucket.end(),
        [key = rhs.first](auto value) { return value.first == key; });
    if (insertPos != bucket.end()) return std::pair<Iterator,bool>(&*insertPos,false);
    bucket.push_front(std::move(rhs));
    return std::pair<Iterator,bool>(&bucket.front(),true);
  }
  std::vector<std::forward_list<ValueType, TAllocator>> data;
};
}  // namespace WinstJackonw
